
#include <stdio.h>
#include <stdlib.h>

#include "table.h"
#include "sort.h"

/**
 * 打印结果
 * @param indexs
 * @param length
 */
void printResult(int *indexs, int length);

/**
 * 暴力法
 * @param nums
 * @param numSize
 * @param target
 * @param returnSize
 * @return
 */
int *twoSum1(int *nums, int numSize, int target, int *returnSize);

/**
 * 散列法
 * @param nums
 * @param numSize
 * @param target
 * @param returnSize
 * @return
 */
int *twoSum2(int *nums, int numSize, int target, int *returnSize);

/**
 * 排序二分查找法
 * @param nums
 * @param numSize
 * @param target
 * @param returnSize
 * @return
 */
int *twoSum3(int *nums, int numSize, int target, int *returnSize);

int *twoSum4(int *nums, int numSize, int target, int *returnSize);

/**
 * 力扣：1、两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

 */
int main() {
    int nums[] = {5, 75, 25};
    int target = 100;
    int length = sizeof(nums) / sizeof(int);
    int *returnSize = (int *) malloc(sizeof(int));

    int *index1s = twoSum1(nums, length, target, returnSize);
    printf("暴力法\n");
    printResult(index1s, *returnSize);
    int *index2s = twoSum2(nums, length, target, returnSize);
    printf("散列法\n");
    printResult(index2s, *returnSize);
    int *index3s = twoSum3(nums, length, target, returnSize);
    printf("排序二分法\n");
    printResult(index3s, *returnSize);

    printf("快慢指针法\n");
    int *index4s = twoSum4(nums, length, target, returnSize);
    printResult(index4s, *returnSize);
    free(returnSize);
    free(index1s);
    free(index2s);
    free(index3s);
    free(index4s);
    index1s = NULL;
    index2s = NULL;
    index3s = NULL;
    index4s = NULL;
    returnSize = NULL;
    return 0;
}

void printResult(int *indexs, int length) {
    if (length == 2) {
        printf("[%d,%d]", indexs[0], indexs[1]);
        printf("\n");
    }
}

int *twoSum4(int *nums, int numSize, int target, int *returnSize) {
    int slow = 0;
    int quick = 1;
    while (quick < numSize) {
        if (nums[slow] + nums[quick] == target) {
            *returnSize = 2;
            int *ret = (int *) malloc(sizeof(int) * 2);
            ret[0] = slow;
            ret[1] = quick;
            return ret;
        }
        if (quick == numSize - 1) {
            slow += 1;
            quick = slow + 1;
        } else {
            quick += 1;
        }
    }
    *returnSize = 0;
    return NULL;
}

int *twoSum3(int *nums, int numSize, int target, int *returnSize) {
    int *sort = mergeSort(nums, numSize);
    for (int i = 0; i < numSize; ++i) {
        int goal = target - nums[i];

        int index = search(sort, numSize, goal);
        if (index != -1) {
            int sourceIndex = getIndex(nums, numSize, goal, i + 1);
            if (sourceIndex != -1) {
                *returnSize = 2;
                int *ret = (int *) malloc(sizeof(int) * 2);
                ret[0] = i;
                ret[1] = sourceIndex;
                return ret;
            }
        }
    }
    *returnSize = 0;
    free(sort);
    sort = NULL;
    return NULL;
}

int *twoSum2(int *nums, int numSize, int target, int *returnSize) {

    HashTable *map = create();
    for (int i = 0; i < numSize; ++i) {
        int num = target - nums[i];
        Entry *node = map->get(map, num);
        if (node != NULL) {
            while (node != NULL) {
                if (node->val != i && (nums[i] + node->key == target)) {
                    *returnSize = 2;
                    int *ret = (int *) malloc(sizeof(int) * 2);
                    ret[0] = i;
                    ret[1] = node->val;
                    map->clear(map);
                    return ret;
                }
                node = node->next;
            }
        }
        map->put(map, nums[i], i);
    }
    *returnSize = 0;
    map->clear(map);
    return NULL;
}


int *twoSum1(int *nums, int numSize, int target, int *returnSize) {
    for (int i = 0; i < numSize; ++i) {
        for (int j = i + 1; j < numSize; ++j) {
            if (target == nums[i] + nums[j]) {
                *returnSize = 2;
                int *ret = (int *) malloc(sizeof(int) * 2);
                ret[0] = i;
                ret[1] = j;
                return ret;

            }
        }
    }
    *returnSize = 0;
    return NULL;
}